//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 测试用例的答案是一个 32-位 整数。 
//
// 子数组 是数组的连续子序列。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -10 <= nums[i] <= 10 
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 
// 
//
// Related Topics 数组 动态规划 👍 2164 👎 0


package com.tyrone.leetcode.editor.cn;


import java.util.Arrays;

public class MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new MaximumProductSubarray().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用动态规划
         * 由于存在负数，所以要分类讨论，碰到是分数的时候会让最小的变成最大的
         * 将dpmin也保存下来，
         * 判断dpMax的时候判断   dpMax[i]*dpMax[i-1]  nums[i]  dpMin[i-1]*nums[i] 三者最大值
         * 判断dpMin的时候判断
         *
         * @param nums
         * @return
         */
//    public int maxProduct(int[] nums) {
//        int[] dpMax = new int[nums.length];
//        int[] dpMin = new int[nums.length];
//        Arrays.fill(dpMax,Integer.MIN_VALUE);
//        Arrays.fill(dpMin,Integer.MAX_VALUE);
//        dpMax[0] = dpMin[0] = nums[0];
//        int n = nums.length;
//        for (int i = 1; i < n; i++) {
//            dpMax[i]  = Math.max(nums[i]*dpMax[i-1],Math.max(nums[i],dpMin[i-1]*nums[i]));
//            dpMin[i]  = Math.min(nums[i]*dpMin[i-1],Math.min(nums[i],dpMax[i-1]*nums[i]));
//        }
//        int max = dpMax[0];
//        for (int i = 0; i < dpMax.length; i++) {
//            max = Math.max(max,dpMax[i]);
//        }
//        return max;
//    }


        /**
         * 直接用两个变量就行了，因为i使用只和i-1有关系
         * @param nums
         * @return
         */
        public int maxProduct(int[] nums) {
            int n = nums.length;
            int curr = nums[0];
            int max = nums[0];
            int min = nums[0];

            for (int i = 1; i < nums.length; i++) {
                //如果当前小于0 那么 最小值 和最大值互换
                if (nums[i]<0){
                    int tmp = max;
                    max = min;
                    min = tmp;
                }
                max = Math.max(nums[i],max*nums[i]);
                min = Math.min(nums[i],min*nums[i]);
                curr = Math.max(max,curr);
            }
            return curr;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}